package main.Q301_400;

public class Q301_310 {
    public static void main(String[] args) {
        System.out.println("Question301：");
        System.out.println("Question302：");
        System.out.println("Question303：区域和检索-数组不可变");
        System.out.println("Question304：二维区域和检索-矩阵不可变");
        System.out.println("Question305：");
        System.out.println("Question306：");
        System.out.println("Question307：区域和检索-数组可修改");
        System.out.println("Question308：");
        System.out.println("Question309：最佳买卖股票时机含冷冻期");
        System.out.println("Question310：");
    }
}

class Question303{
    int[] arrs;
    public Question303(int[] nums) {
        int n= nums.length;
        arrs=new int[n+1];
        for (int i=0;i<n;i++) arrs[i+1]=arrs[i]+nums[i];
    }

    public int sumRange(int left, int right) {
        return arrs[right+1]-arrs[left];
    }
}

class Question304{
    private int[][] Matrix;
    public Question304(int[][] matrix) {
        this.Matrix=matrix;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum=0;
        for (int i=row1;i<=row2;i++){
            for (int j=col1;j<=col2;j++)
                sum+=this.Matrix[i][j];
        }
        return sum;
    }
}

class Question307{
    private int[] Nums;
    public Question307(int[] nums) {
        this.Nums=nums;
    }

    public void update(int index, int val) {
        Nums[index]=val;
    }

    public int sumRange(int left, int right) {
        int sum=0;
        while (left<=right)
            sum+=Nums[left];
        return sum;
    }
}

class Question309{
    public static int maxProfit(int[] prices) {
        int length= prices.length;
        int[][] dp=new int[length][3];
        for (int i=0;i<length;i++){
            if (i==0){
                dp[i][0]=0-prices[i];//当天有股票
                dp[i][1]=0;//当天没有股票且不在冷冻期
                dp[i][2]=0;//当天没有股票且在冷冻期
            }else {
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);//i-1天有股票或者i-1天不在冷冻期并且在i天买入股票
                dp[i][1]=Math.max(dp[i-1][1],dp[i-1][2]);//i-1天没有股票(在冷冻期或不在冷冻期)
                dp[i][2]=dp[i-1][0]+prices[i];//i-1天有股票i天卖出
            }
        }
        return Math.max(dp[length-1][1],dp[length-1][2]);
    }
}